#define _CRT_SECURE_NO_WARNINGS  1


class Solution {
public:
    bool find(TreeNode* tree, TreeNode* x)
    {
        if (tree == nullptr)
            return false;

        return tree == x || find(tree->left, x) || find(tree->right, x);
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
    {
        if (root == nullptr)
            return root;

        if (p == root || q == root)
        {
            return root;
        }

        bool pl, pr, ql, qr;
        pl = find(root->left, p);
        pr = !pl;

        ql = find(root->left, q);
        qr = !ql;

        if (pl && ql)
        {
            return lowestCommonAncestor(root->left, p, q);
        }
        else if (pr && qr)
        {
            return lowestCommonAncestor(root->right, p, q);
        }
        else
        {
            return root;
        }
    }
};